package com.tyning.newcode.jz28;

/**
 * 剑指 Offer 28. 对称的二叉树
 * 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
 * <p>
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 * <p>
 * 1
 * / \
 * 2   2
 * / \ / \
 * 3  4 4  3
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 * <p>
 * 1
 * / \
 * 2   2
 * \   \
 * 3    3
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 * 示例 2：
 * <p>
 * 输入：root = [1,2,2,null,3,null,3]
 * 输出：false
 * <p>
 * <p>
 * 限制：
 * <p>
 * 0 <= 节点个数 <= 1000
 * https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
 * 注意：本题与主站 101 题相同：https://leetcode-cn.com/problems/symmetric-tree/
 */

import com.tyning.utils.TreeNode;
import com.tyning.utils.TreeNodeUtil;

/**
 * @author haining
 */
public class Solution {

    public static void main(String[] args) {
        TreeNode treeNodeA = TreeNodeUtil.createTreeNode(new Integer[]{4, 2, 7, 1, 3, 6, 9});
        Solution solution = new Solution();
        solution.isSymmetric(treeNodeA);
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return false;
        }
        return isEq(root.left, root.right);
    }

    public boolean isEq(TreeNode rootLeft, TreeNode treeNodeRight) {
        if (rootLeft == null && treeNodeRight == rootLeft){
            return true;
        }
        if ((rootLeft == null || treeNodeRight == null) && treeNodeRight != rootLeft){
            return false;
        }
        return rootLeft.val == treeNodeRight.val && isEq(rootLeft.left, treeNodeRight.right) && isEq(rootLeft.right, treeNodeRight.left);
    }


}
